package leetcode_300;

import java.util.HashMap;

/**
 *@author 周杨
 *ImplementTrie_PrefixTree_208 构造字典树 用以搜索某个单词 或者前缀
 *describe:用哈希表 每个节点对应26个哈希树节点 并用标记位表示此处是否构成了单词  AC 25%
 *2018年6月14日 上午11:15:11
 */
public class ImplementTrie_PrefixTree_208 {
	private TrieNode root;

	class TrieNode {
	    boolean isWord;
	    HashMap<Character, TrieNode> nexts;

	    public TrieNode() {
	        nexts = new HashMap<Character, TrieNode>();
	    }
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	/** Initialize your data structure here. */
    public ImplementTrie_PrefixTree_208() {
    	root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
    	char[] s = word.toCharArray();

        TrieNode p = root;
        int i = 0, n = s.length;

        // traverse existing
        while (i < n) {
            TrieNode next = p.nexts.get(s[i]);
            if (next != null) {
                p = next;
                i ++;
            } else {
                break;
            }
        }
        
        // append new nodes
        while (i < n) {
            TrieNode newTrie = new TrieNode();
            p.nexts.put(s[i], newTrie);
            p = newTrie;
            i ++;
        }

        // set word end
        p.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    	TrieNode p = root;

        for (int i = 0; i < word.length(); i ++) {
            TrieNode child = p.nexts.get(word.charAt(i));
            if (child == null) {
                return false;
            }
            p = child;
        }

        return p.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
    	 TrieNode p = root;

         for (int i = 0; i < prefix.length(); i ++) {
             TrieNode child = p.nexts.get(prefix.charAt(i));
             if (child == null) {
                 return false;
             }
             p = child;
         }

         return true;
    }

}
